package dame;

import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedsize;
    public TestHeap(){
        this.elem = new int[10];
    }

    public void initElem(int[] array){       //给数组初始化
        for (int i=0;i<array.length;i++){
            this.elem[usedsize] = array[i];
            this.usedsize++;
        }
    }

    public void createTestHeap(){      //大根堆调整
        for (int parent = (usedsize-1-1)/2;parent>=0;parent--){
            siftDown(parent,this.usedsize);
        }
    }

    /*parent是调整的起始位置
    * usedsize 判断每颗子树什么时候调整结束*/
   private void siftDown(int parent, int usedsize) {
        int child = parent*2+1;
        while (child<usedsize){
            if (child+1<usedsize&&elem[child]<elem[child+1]){
                swop(elem,child,parent);
            }else {
                break;
            }
        }
    }
    private void swop(int[] elem,int i,int j){  //交换child和parent
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = elem[i];
    }

    public void offer(int val){  //堆的插入
       if (isFull()){
           elem = Arrays.copyOf(elem,2*elem.length);
       }
       this.elem[usedsize] = val;
       siftup(usedsize );
       usedsize++;
    }

    private void siftup(int child) {
       int parent = (child-1)/2;
       while (parent>=0){
           if (elem[child]>elem[parent]){
               swop(elem,child,parent);
               child = parent;
               parent = (child-1)/2;
           }else {
               break;
           }
       }
    }

    private boolean isFull(){
       return this.usedsize==elem.length;
}

public int poop(){  //堆的删除
       if (isEmpyt()){
           return -1;
       }
    int val = elem[0];
   swop(elem,0,usedsize-1);
   siftDown(0,usedsize-1);
   usedsize--;
   return val;
}
private boolean isEmpyt(){
       return usedsize==0;
}

public int peek(){  //获取堆头元素
       if (isEmpyt()){
           return -1;
       }
       return elem[0];
}

public void haspsort(){  //堆排序， 大根堆
       int end = usedsize-1;
       while (end>0){
           swop(elem,0,end);
           siftDown(0,end);
           end--;
       }
}
}
